#include "memalloc.hpp"


MemAllocImpl *MemAllocImpl::inst;
int MemAllocImpl::PAGESIZE;
#ifdef LINUX
inline int DownLog(uint64_t x){
    return x? (63 - __builtin_clzll(x)) : -1;
}

#else
static const int MultiplyDeBruijnBitPosition[64] = 
{
    0,  1,  2, 53,  3,  7, 54, 27,
    4, 38, 41,  8, 34, 55, 48, 28,
   62,  5, 39, 46, 44, 42, 22,  9,
   24, 35, 59, 56, 49, 18, 29, 11,
   63, 52,  6, 26, 37, 40, 33, 47,
   61, 45, 43, 21, 23, 58, 17, 10,
   51, 25, 36, 32, 60, 20, 57, 16,
   50, 31, 19, 15, 30, 14, 13, 12,
};


//round down of log_2(size)
inline int DownLog(uint64_t x){
    if (!x) return 0; //convention
    x /= 2;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return MultiplyDeBruijnBitPosition[(uint64_t)((x+1)*0x022fdd63cc95386d) >> 58];            
}
#endif


MemAllocImpl::MemAllocImpl(size_t mem_size, uint64_t swap_size, const std::string& swap_path) {
	if (mem_size > swap_size) {
		throw MemAllocException(MemAllocException::E_INVALID_INIT_SIZES, "swap < mem");
	}
	s_size = total_free = swap_size;
	m_size = mem_free = mem_size ? mem_size : 1;
	inst = this;
#ifdef WINDOWS
	try {
		mem = new char[m_size];
	}
	catch (...) {
		throw MemAllocException(MemAllocException::E_2BIG, "mem size is too big");
	}


	PAGESIZE = 4096;
	pFile = fopen(swap_path.c_str(), "w+b");
	if (!pFile){
#endif
#ifdef LINUX
        const int opt_num = 1024;          //optimal number of "pages" fitting in m_size. TODO research
        PAGESIZE = sysconf(_SC_PAGESIZE);
        
	//round up (m_size / opt_num) to multiple of pagesize
        PAGESIZE = (((m_size-1)/opt_num/PAGESIZE)+1)*PAGESIZE;

	dFile = open(swap_path.c_str(), O_RDWR | O_CREAT, S_IRWXU);
        
	if (dFile == -1){
#endif

		if (errno == EACCES)
			throw MemAllocException(MemAllocException::E_ACCES, "access to swap file is denied");
		else if (errno == EFAULT)
			throw MemAllocException(MemAllocException::E_FAULT, "bad swap path");
		else if (errno == EBUSY)
			throw MemAllocException(MemAllocException::E_BUSY, "file is busy");
		else if (errno == ENOTDIR)
			throw MemAllocException(MemAllocException::E_NOTDIR, "dir is not a dir");
		throw MemAllocException((MemAllocException::ErrorCode)errno, "file exception");
	}
        
#ifdef LINUX
        if (posix_fallocate(dFile, 0, swap_size)){
            if (errno == ENOSPC)
		throw MemAllocException(MemAllocException::E_NOSPC, "no enough space");
            else if (errno == EFBIG)
		throw MemAllocException(MemAllocException::E_FBIG, "swap file is too big");
            throw MemAllocException((MemAllocException::ErrorCode)errno, "file exception");
        }
        mem = (char*) mmap(0, m_size, PROT_READ | PROT_WRITE, MAP_SHARED, dFile, 0);
        if (mem == MAP_FAILED){
            throw; //mem too big!!! TODO choose error!!!
        }
#endif
	//calculate numbers of maximum sizes fitting in memory and swap
	uint64_t temp = DownLog(swap_size / min_chunk);
	N_swap = temp != -1 ? temp: 0;
	temp = DownLog(m_size / PAGESIZE);
	N_mem = temp != -1 ? temp : 0;

        const int spread = 20;       //log_2(chunk_max_size/chunk_min_size)
	if (N_swap > spread){
		N_swap = spread;
	}
	int tmp = spread - DownLog(PAGESIZE) + DownLog(min_chunk);
	if (N_mem > tmp){
		N_mem = tmp;
	}
	try{
		free_swap_chunks = new List<uint64_t>[N_swap + 1];
		free_mem_pages = new List<size_t>[N_mem + 1];
		released_mem_pages = new ReleasedList[N_mem + 1];
	}
	catch(...){
		throw MemAllocException(MemAllocException::E_NOTDIR, "dir is not a dir");
	}

	//filling up sets of free blocks
	size_t tmp_size = (1 << N_mem);	//all in PAGESIZE units
	size_t p = 0;
	for (int size_num = N_mem; size_num >= 0; --size_num, tmp_size /= 2){
		while ((p + tmp_size) * PAGESIZE <= m_size){
			free_mem_pages[size_num].Insert(p, tmp_size, false); //without merging
			p += tmp_size;
		}
	}

	tmp_size = (1 << N_swap);
	uint64_t offset = 0;
	for (int size_num = N_swap; size_num >= 0; --size_num, tmp_size /= 2){
		while ((offset + tmp_size) * min_chunk <= swap_size){
			free_swap_chunks[size_num].Insert(offset, tmp_size, false);
			offset += tmp_size;
		}
	}
	count_page_swap = new CountPageSwap[(swap_size - 1) / PAGESIZE + 1];
}

MemAllocImpl::~MemAllocImpl() {

#ifdef WINDOWS
        delete[] mem;
#endif
#ifdef LINUX
        munmap(mem, m_size);
#endif           

        
	delete[] free_swap_chunks;
	delete[] free_mem_pages;
	delete[] released_mem_pages;
	delete[] count_page_swap;
        
        
        inst = 0;
#ifdef WINDOWS
        fclose(pFile);
#endif
#ifdef LINUX
	close(dFile);
#endif
        //this memory would be freeed even without these lines, but only 
        //at the end of the program execution
        Garbage<size_t>::Wipe();
        Garbage<uint64_t>::Wipe();
        Garbage<SmartPtr<char>>::Wipe();
        Garbage<SmartPtrImpl>::Wipe();
}


SmartPtrImpl* MemAllocImpl::Alloc(size_t size) {
	if (!inst){
		throw MemAllocException(MemAllocException::E_UNINITIALIZED, "uninited");
	} 
	if (size > total_free) {
		throw MemAllocException(MemAllocException::E_2BIG, "Total size > swap size");
	}

        if (size > m_size) {
		throw MemAllocException(MemAllocException::E_2BIG, "Size > memory");
	}
        total_free -= size;
	int n = DownLog((size - 1) / min_chunk) + 1; //number of a chunk size (0 .. N)
	if (n > N_swap){
		throw MemAllocException(MemAllocException::E_2BIG, "Fragmentaion of mem!");
	}
        
        SmartPtrImpl *ptr;
        try{
            ptr = new SmartPtrImpl();
        }
        catch(...){
            throw;//out of memory!!!
        }
        ptr->state = SmartPtrImpl::UNINITED;

	ptr->size = size;
	ptr->sz_num = n;
	ptr->page_size_num = DownLog((size - 1) / PAGESIZE) + 1;
	return ptr;
}


void MemAllocImpl::Free(SmartPtrImpl* smartptr, bool forced)
{
        if (!inst){
		return;
	}
        if (smartptr->state == SmartPtrImpl::UNINITED){
            inst->total_free += smartptr->size;
            smartptr->state = SmartPtrImpl::INVALID;
            return;
        }
        if (forced && smartptr->state == SmartPtrImpl::INVALID){
            return;
        }
        
	if (smartptr->get_count > 0 && !forced){
		throw MemAllocException(MemAllocException::E_ACTIVE_MEMORY_FREE
			, "Tried to free memory without release");
	}
	if (!forced && smartptr->state == SmartPtrImpl::INVALID){
                //block is freeed, but free was called on it (not from SP destructor)
		throw MemAllocException(MemAllocException::E_ACTIVE_MEMORY_FREE
			, "double free"); //!!!! add another error code
	}

	int sz_num = smartptr->sz_num;
	inst->total_free += smartptr->size;
	List<uint64_t>::Merge(inst->free_swap_chunks, sz_num, inst->N_swap, smartptr->offset);

	size_t page_num = smartptr->offset * min_chunk / PAGESIZE;
	int cnt = --(inst->count_page_swap[page_num].alloc_count);

	if (smartptr->state == SmartPtrImpl::IN_MEM){
		size_t size = smartptr->size;
		if (cnt == 0){
			List<size_t>::Merge(inst->free_mem_pages, smartptr->page_size_num, inst->N_mem, page_num);
		}
	}
	smartptr->state = SmartPtrImpl::INVALID;

}
